import java.io.IOException;
import java.text.DecimalFormat;

/**
 * Reference of Sudoku backtracking algorithm (C++): 
 * 		http://fr.openclassrooms.com/informatique/cours/le-backtracking-par-l-exemple-resoudre-un-sudoku/codage-de-la-solution
 * 
 * Reference of Sudoku bruteforce algorithm (Java):
 * 		http://code.activestate.com/recipes/577314-sudoku-solver-bruteforce/
 */

public class Main {

	static int noeud = 0;
	public static void main(String[] args) throws IOException {
			
		ReadSudokuFile.loadSudoku(FileUtil.getInstance().openReader(args[0]));
		int grid[][] = ReadSudokuFile.sudoku;
		
		 printSudoku(grid);
		 Boolean validSudoku = false;
		 long startTime  = 0;
		 long endTime = 0;
		 if (args.length == 2) {
			 startTime = System.nanoTime();
			 validSudoku = solveSudokuBruteforce(grid);
			 endTime = System.nanoTime();
		 }
		 else
		 {
			 startTime = System.nanoTime();
			 validSudoku = solveSudokuBackTracking(grid,0);
			 endTime = System.nanoTime();
		 }
		 DecimalFormat df = new DecimalFormat();
		 df.setMaximumFractionDigits(2);
		 System.out.print((double)((endTime - startTime)/1000000000.0));
		 System.out.print("\n\n");
		 if(validSudoku)
			 printSudoku(grid);
		 else
			 System.out.print("Sudoku non valide");
	}
	
	private static void printSudoku(int[][] grid) {
		  for (int i=0; i<9; i++)
		    {
		        for (int j=0; j<9; j++)
		        {
		        	if (j%3 == 0 && j != 0)
		        		 System.out.print("|");
		        	else 
		        		System.out.print(" ");
		        	System.out.print(grid[i][j]);
		        }
		        System.out.print('\n');
		        if ((i+1)%3 == 0 && (i+1)!=9)
		        	System.out.print("------------------ \n" );
		    }
	}
	
	/**
	 * Sudoku backtracking algorithm
	 */
	
	private static Boolean solveSudokuBackTracking(int[][] grid, int index) {
		if (index == 9*9)
	        return true;
	 
	    int line = index/9;
	    int column = index%9;
	 
	    if (grid[line][column] != 0)

    return solveSudokuBackTracking(grid, index+1);
	 
	    for (int num=1; num <= 9; num++)
	    {
	        if (notInLine(num,grid,line) && notInColumn(num,grid,column) && notInSquare(num,grid,line,column))
	        {
	            grid[line][column] = num;
	 
	            if ( solveSudokuBackTracking(grid, index+1))
	                return true;
	        }
	    }
	    grid[line][column] = 0;
	 
	    return false;
	}
	
private static Boolean notInLine (int num, int grid[][], int line)
{
    for (int j=0; j < 9; j++)
        if (grid[line][j] == num)
            return false;
    return true;
}
 
private static Boolean notInColumn (int num, int grid[][], int column)
{
    for (int i=0; i < 9; i++)
        if (grid[i][column] == num)
            return false;
    return true;
}
 
private static Boolean notInSquare (int num, int grid[][], int line, int column)
{
    int tempLine = line-(line%3); 
    int tempColumn = column-(column%3);
       for (line= tempLine; line < tempLine+3; line++)
        for (column=tempColumn; column < tempColumn+3; column++)
           if (grid[line][column] == num)
                return false;
    return true;
}

/**
 * Sudoku bruteforce algorithm
 */
private static Boolean solveSudokuBruteforce(int[][] grid)
{	
	int line=0;
	int column=0;
	boolean found = false;
	
	for(line = 0;line < 9; line ++)
	{
		for(column = 0;column < 9; column++)
		{
			if(grid[line][column] == 0)
			{
				found = true;
				break;
			}
		}
		if( found )
			break;
	}
	
	if(!found)
		return true;
	
	boolean digits[] = new boolean[11];
	
	for(int i = 0; i < 9; i++)
	{
		digits[grid[line][i]] = true;
		digits[grid[i][column]] = true;
	}
	
	int bx = 3 * (line/3);
	int by = 3 * (column/3);
	
	for(int lineSquare =0;lineSquare<3;lineSquare++)
		for(int columnSquare = 0; columnSquare < 3; columnSquare++)
			digits[grid[bx+lineSquare][by+columnSquare]] = true;
	
	for(int i = 1 ; i <= 9; i++)
	{
		if(!digits[i] )
		{
			grid[line][column] = i;
			if(solveSudokuBruteforce(grid))
				return true;
			grid[line][column] = 0;
		}
	}
	return false;
}

}